package com.doublecheck.SimHash;

import com.doublecheck.WordGeter.*;

import java.util.*;
import java.math.BigInteger;

/**
 * simhash算法主要在数据量特别大的时候效果显著：对每条文本根据SimHash 算出签名后，再计算两个签名的海明距离（两个二进制异或后1的个数）即可。
 * 根据经验值，对64位的SimHash，海明距离在3以内的可以认为相似度比较高。假设对64位的SimHash，查找海明距离在3以内的所有签名。可以把64位的二进制签名均分成4块，每块16位。根据鸽巢原理（也称抽屉原理，见组合数学），如果两个签名的海明距离在3以内，它们必有一块完全相同。
 * 把上面分成的4块中的每一个块分别作为前16位来进行查找。建立倒排索引。如果库中有2^34个（大概10亿）签名，那么匹配上每个块的结果最多有2^(34-16)=262144个候选结果(假设数据是均匀分布，16位的数据，产生的像限为2^16个，则平均每个像限分布的文档数则2^34/2^16=2^(34-16))，四个块返回的总结果数为4*262144（大概100万）。原本需要比较10亿次，经过索引，大概就只需要处理100万次了。由此可见，确实大大减少了计算量。
 * 但本程序数据量远没有那么大，至于这样做不一定有正面的效果。
 */

public class SimHash {
     public int hashBits = 64;// hash值的bit数
     public BigInteger intSimHash;// 十进制的指纹
     public String strSimHash;// 二进制的指纹

     public void getTxtHash(WordGeter txtInfo) {
          int[] eachbit = new int[64];
          for(int i=0;i<=this.hashBits-1;i++)
          eachbit[i]=0;
          intSimHash=new BigInteger("0");
          Set<String> keySet = txtInfo.weight.keySet();
          Iterator<String> it = keySet.iterator();
          while (it.hasNext()) {
               String word = it.next();
               BigInteger wordhash = getWordHash(word);
               Integer thisweight = txtInfo.weight.get(word);
               for (int i = 0; i < this.hashBits; i++) {
                    BigInteger bitmask = new BigInteger("1").shiftLeft(i);
                    if (wordhash.and(bitmask).signum() != 0)
                         eachbit[i] += thisweight;
                    else
                         eachbit[i] -= thisweight;
               }
          }
          StringBuffer simHashBuffer = new StringBuffer();
          for (int i = 0; i < this.hashBits; i++) {
               if (eachbit[i] >= 0) {
                    this.intSimHash = this.intSimHash.add(new BigInteger("1").shiftLeft(i));
                    simHashBuffer.append("1");
               } else
                    simHashBuffer.append("0");
          }
          this.strSimHash = simHashBuffer.toString();
          return;
     }

     private BigInteger getWordHash(String word) {
          if (word == null || word.length() == 0) {
               return new BigInteger("0");
          } else {
               // 当sourece 的长度过短，会导致hash算法失效，因此需要对过短的词补偿
               while (word.length() < 3)
                    word = word + word.charAt(0);
               char[] wordArray = word.toCharArray();
               BigInteger wordhash = BigInteger.valueOf(((long) wordArray[0]) << 7);
               BigInteger m = new BigInteger("1000003");
               BigInteger mask = new BigInteger("2").pow(this.hashBits).subtract(new BigInteger("1"));
               for (char item : wordArray) {
                    BigInteger temp = BigInteger.valueOf((long) item);
                    wordhash = wordhash.multiply(m).xor(temp).and(mask);
               }
               wordhash = wordhash.xor(new BigInteger(String.valueOf(word.length())));
               if (wordhash.equals(new BigInteger("-1"))) {
                    wordhash = new BigInteger("-2");
               }
               return wordhash;
          }
     }

}